/*
https://leetcode.cn/problems/kskhHQ/solution/jiantu-by-endlesscheng-rkra/
 */
public class SolutionLCP71 {

    static class Bing{
        int[] b;

        public Bing(int n){
            b=new int[n];
            for (int i=0;i<n;i++){
                b[i]=i;
            }
        }

        public void union(int x,int y){
            int xx=find(x);
            int yy=find(y);
            if (xx!=yy){
                b[xx]=yy;
            }
        }

        public int find(int k){
            return b[k]==k?k:(b[k]=find(b[k]));
        }
    }

    public int reservoir(String[] shape) {
        int n=shape.length,m=shape[0].length();
        int[][] u=new int[n+2][m+2];
        int[][] d=new int[n+2][m+2];
        int[][] l=new int[n+2][m+2];
        int[][] r=new int[n+2][m+2];
        int count=0;
        for (int i=1;i<n+1;i++){
            for (int j=1;j<m+1;j++){
                u[i][j]=count++;
                d[i][j]=count++;
                l[i][j]=count++;
                r[i][j]=count++;
            }
        }
        for (int i=1;i<n+1;i++){
            l[i][m+1]=count;
            r[i][0]=count;
        }
        for (int i=1;i<m+1;i++){
            u[n+1][i]=count;
        }
        Bing bing=new Bing(count+1);
        boolean[] ok=new boolean[count+1];
        for (int i=n;i>=1;i--){
            for (int j=0;j<m+1;j++){
                bing.union(r[i][j],l[i][j+1]);
            }
            for (int j=1;j<m+1;j++){
                bing.union(d[i][j],u[i+1][j]);
                char ch=shape[i-1].charAt(j-1);
                if (ch=='.'){
                    bing.union(d[i][j],r[i][j]);
                    bing.union(d[i][j],u[i][j]);
                    bing.union(d[i][j],l[i][j]);
                }else if (ch=='l'){
                    bing.union(l[i][j],d[i][j]);
                    bing.union(u[i][j],r[i][j]);
                }else {
                    bing.union(l[i][j],u[i][j]);
                    bing.union(d[i][j],r[i][j]);
                }
            }
            for (int j=1;j<m+1;j++){
                ok[l[i][j]]=bing.find(l[i][j])!=bing.find(count);
                ok[r[i][j]]=bing.find(r[i][j])!=bing.find(count);
                ok[d[i][j]]=bing.find(d[i][j])!=bing.find(count);
                ok[u[i][j]]=bing.find(u[i][j])!=bing.find(count);
            }
        }
        for (int i=1;i<m+1;i++){
            bing.union(u[1][i],count);
        }
        int ans=0;
        for (int i=0;i<count;i++){
            if (ok[i] && bing.find(i)==bing.find(count)){
                ans++;
            }
        }
        return ans/2;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionLCP71().reservoir(new String[]{"....rl","l.lr.r",".l..r.","..lr.."}));
    }
}
